1. Technical Field
The present invention relates to network communications and more particularly to systems and methods for traceback in networks to identify and prevent false data injection.
2. Description of the Related Art
Packet traceback is a technique to identify the true origin of a packet and the path it has traversed in a network. It is widely used to combat emerging denial of service (DoS) attacks, where the source address of attack packets is usually “forged” by the attackers to conceal their identities.
There have been a number of IP packet traceback schemes for the wired Internet. For example, a probabilistic packet marking (PPM) scheme has been proposed. In PPM schemes, with certain probability, a router “marks” some information into the packet that the router forwards. The information conveys the identity of the router, or the link between two adjacent routers. After collecting the markings from different routers, the destination can reconstruct the path which the packets have traversed.
An algebraic approach has been proposed where the path information is encoded in a polynomial, f(x), whose coefficients are determined by the identities of the routers along a path. Each packet carries a sample x, and all routers along a path will collectively compute f(x). After collecting sufficient (x, f(x)) value pairs, the destination can derive the coefficients and eventually infer the identities of routers.
In other techniques, each router is required to store the previously forwarded packets for an extended period of time. By querying the routers whether they forwarded one packet in the past, the destination can reconstruct the forwarding path. Routers may also send out-of-band traceback messages to the source or destination with small probability. Collecting these messages allows the destination to construct the path.
These schemes were designed under a limited threat model, which becomes insufficient in many applications, e.g., in wireless mesh and sensor networks. Most of these conventional techniques assume that the intermediate nodes (routers) are not compromised. This may not be true in reality, especially in wireless mesh or sensor networks, where the nodes are vulnerable to physical capture and compromise. In these schemes, even a single compromised intermediate node can prevent the true origin of packets from being identified. The compromised node can even forge the markings and trick the victim into tracing back to arbitrary incorrect origins.
In addition, many schemes require a large number of packets be collected, or intermediate nodes store large amounts of audit traces to accurately pinpoint the locations of perpetrators. These may not be an issue in the Internet, but face severe practical obstacles in wireless mesh and sensor networks, which have stringent bandwidth, energy, and storage resources.